﻿using System;
namespace HorsePower
{
    class Program
    {
        static void Main()
        {
            int[] Start = new int[] { 0, 0 }; //стартовые координаты
            int[] Finish = new int[] { 4, 3 };// финишные координаты
            Console.WriteLine("Ход конём");
            Console.WriteLine("Стартовая позиция:x= {0}, y= {1}", Start[0], Start[1]);
            Console.WriteLine("Финишная позиция:x= {0}, y= {1}", Finish[0], Finish[1]);
            Console.WriteLine();
            HorseMove New = new HorseMove();
            New.CreateBoard(Start, Finish);  //предстартовые данные
        }
    }
    public class HorseMove
    {
        public int Check            //для проверки на бесконечность ходов
        {  
            get { return _check; }
            set { _check = 0; }
        }

        public int _n = 10;         //метрика доски
        public int[,] Board;
        public int[] turnHorizont = new int[] { 1, 2, 2, 1, -1, -2, -2, -1 }; //движение по координате x
        public int[] turnVertical = new int[] { 2, 1, -1, -2, -2, -1, 1, 2 }; //движение по координате y

        public void CreateBoard(int[] Start, int[] Finish)
        {
            Board = new int[_n + 4, _n + 4];        //игровое поле
            for (int i = 0; i < _n + 4; i++)        //заполняем доску
            {
                for (int j = 0; j < _n + 4; j++)
                {
                    Board[i, j] = 0;                //по умолчанию значение каждой ячейки = 0
                }
            }
            Start[0] = Start[0] + 2;                // в оболочке предполагается на 2 ряда ячеек больше с каждой стороны
            Start[1] = Start[1] + 2;                // для предотвращения выхода за границы доски
            Finish[0] = Finish[0] + 2;              // поэтому к координатам Start и Finish +2
            Finish[1] = Finish[1] + 2;
            Board[Start[0], Start[1]] = 1;          //идентификатор старта
            Board[Finish[0], Finish[1]] = -1;       //идентификатор финиша
            int _MoveCounter = 1;                   //счётчик номера хода
            Go(Board, _MoveCounter);                //начинаем ходить

        }

        public void Go(int[,] Board, int MoveCounter)
        {
            _check++;
            for (int i = 2; i < _n + 2; i++)   //по вертикали
            {
                for (int j = 2; j < _n + 2; j++) //по горизонтали
                {
                    if (Board[i, j] == MoveCounter) //ищем ячейки с предыдущим ходом
                    {
                        MoveCounter++;
                        for (int k = 0; k < 8; k++)
                        {
                            if (Board[i + turnVertical[k], j + turnHorizont[k]] == -1) //проверка на финишность
                            {
                                End(MoveCounter, Board);
                                return;
                            }
                            else if (Board[i + turnVertical[k], j + turnHorizont[k]] > 0) { } //не заполнять уже заполненные клетки
                            else
                            {
                                Board[i + turnVertical[k], j + turnHorizont[k]] = MoveCounter;  //заполняем клетку номером данного хода
                            }
                        }
                    }
                }
            }
            if (_check > 20)     //если за 20 итераций Финиш не достигнут, то считаем что дойти до Финиша невозможно
            {
                Console.WriteLine("Путь к финишной точке не найден");
                for (int i = 0; i < _n + 4; i++)            //выводим конечный рисунок поля
                {                                           //
                    for (int j = 0; j < _n + 4; j++)        //
                    {                                       //
                        Console.Write(Board[i, j] + " ");   //
                    }                                       //
                    Console.WriteLine();                    //
                }
                Console.ReadKey();
                return;
            }
            else
            {
                MoveCounter = 1 + _check;           //дополнительный перебор всех ходов()
                Go(Board, MoveCounter);
            }
        }
        public void End(int Counter, int[,] Board)
        {
            Console.WriteLine();
            Console.WriteLine("Финиш достигнут");
            Console.WriteLine("Нужно {0} ходов для достижения Финиша!", Counter - 1);
            for (int i = 0; i < _n + 4; i++)            //выводим конечный рисунок поля
            {                                           //
                for (int j = 0; j < _n + 4; j++)        //
                {                                       //   
                    Console.Write(Board[i, j] + " ");   //
                }                                       //
                Console.WriteLine();                    //
            }                                           //
            Console.ReadKey();
        }
        private int _check;
    }
}
